// 哈夫曼树节点定义
class HuffmanNode {
  constructor(char, freq, left = null, right = null) {
    this.char = char; // 字符
    this.freq = freq; // 频率
    this.left = left; // 左子节点
    this.right = right; // 右子节点
  }
}

// 构建哈夫曼树
function buildHuffmanTree(charFreqs) {
  // charFreqs: [{char: 'a', freq: 5}, ...]
  const nodes = charFreqs.map(({ char, freq }) => new HuffmanNode(char, freq));

  while (nodes.length > 1) {
    // 按频率升序排序
    nodes.sort((a, b) => a.freq - b.freq);
    // 取出最小的两个节点
    const left = nodes.shift();
    const right = nodes.shift();
    // 合并成新节点
    const newNode = new HuffmanNode(null, left.freq + right.freq, left, right);
    nodes.push(newNode);
  }
  return nodes[0]; // 返回根节点
}

// 生成哈夫曼编码
function generateHuffmanCodes(root) {
  const codes = {};
  function traverse(node, code) {
    if (!node) return;
    if (node.char !== null) {
      codes[node.char] = code;
      return;
    }
    traverse(node.left, code + '0');
    traverse(node.right, code + '1');
  }
  traverse(root, '');
  return codes;
}

// 示例用法
const charFreqs = [
  { char: 'a', freq: 5 },
  { char: 'b', freq: 9 },
  { char: 'c', freq: 12 },
  { char: 'd', freq: 13 },
  { char: 'e', freq: 16 },
  { char: 'f', freq: 45 },
];

const huffmanTree = buildHuffmanTree(charFreqs);
const codes = generateHuffmanCodes(huffmanTree);
console.log('哈夫曼编码:', codes);

// 冒泡排序实现
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// 冒泡排序示例
const arr = [5, 2, 9, 1, 5, 6];
console.log('冒泡排序前:', arr);
console.log('冒泡排序后:', bubbleSort([...arr]));
